// 在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。

#include<bits/stdc++.h>
#include<string>
#include<vector>
#include<list>
#include<unordered_map>
#include<priority_queue>
#include<set>
#include<queue>
using namespace std;

// 看了题解
// 动态规划

// 执行用时：
// 20 ms
// , 在所有 C++ 提交中击败了
// 95.20%
// 的用户
// 内存消耗：
// 10.8 MB
// , 在所有 C++ 提交中击败了
// 90.94%
// 的用户

class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        int h=matrix.size();
        int l=matrix[0].size();
        bool dp[h][l];
        // 当前边长
        int k=0;
        // 标志是否存在当前边长正方形
        bool flag =false;
        while(k<=min(h,l)){
            for(int i=0;i<h-k;i++){
                for(int j=0;j<l-k;j++){
                    if(k==0){
                        dp[i][j] = matrix[i][j]=='1';
                    }
                    else{
                        // 如果不符合会被置为false，因此必定符合上一个k，k=2，则3*3符合则置true
                        dp[i][j] = dp[i][j] && dp[i+1][j] && dp[i][j+1] && dp[i+1][j+1];
                    }
                    if(dp[i][j]){
                        flag = true;
                    }
                }
            }
            // 存在则+1
            if(flag){
                k++;
                flag = false;
            }
            // 上一个k不存在则不可能存在下一个
            else{
                break;
            }
        }
        return k*k;

    }
};